package pers.qianyu.month_202102.date_20210220;

import org.junit.*;

import java.util.*;

/**
 * 697. 数组的度
 * https://leetcode-cn.com/problems/degree-of-an-array/
 * - 思路很巧妙
 *
 * @author mizzle rain
 * @date 2021-02-20 12:07
 */
public class FindShortestSubArray {
    public int findShortestSubArray(int[] nums) {
        int n = nums.length;
        HashMap<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (map.containsKey(x)) {
                int[] arr = map.get(x);
                arr[1] = i;
                arr[2]++;
            } else {
                int[] arr = {i, i, 1};
                map.put(x, arr);
            }
        }
        int maxValue = Integer.MIN_VALUE, minLen = Integer.MAX_VALUE;
        for (int[] x : map.values()) {
            if (maxValue == x[2]) {
                minLen = Math.min(minLen, x[1] - x[0] + 1);
            } else if (maxValue < x[2]) {
                maxValue = x[2];
                minLen = x[1] - x[0] + 1;
            }
        }
        return minLen;
    }

    @Test
    public void test1() {
        int result = new FindShortestSubArray()
                .findShortestSubArray(new int[]{1, 2, 2, 3, 1});
        Assert.assertEquals(2, result);
    }

    @Test
    public void test2() {
        int result = new FindShortestSubArray()
                .findShortestSubArray(new int[]{1, 2, 2, 3, 1, 4, 2});
        Assert.assertEquals(6, result);
    }
}
